package com.leetcode.p0;

public class Test53 {

    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int sum = max;

        for (int i = 1; i < nums.length; i++) {
            if (sum > 0) {
                sum += nums[i];
            } else {
                sum = nums[i];
            }

            max = Math.max(max, sum);
        }

        return max;
    }

    public static void main(String[] args) {
        Test53 test = new Test53();
        int result = test.maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4});
        System.out.println(result);
    }

}
